Dynamic Structural Clustering Unleashed: Flexible Similarities, Versatile Updates and for All Parameters

Abstract

We study structural clustering on graphs in dynamic scenarios, where graphs can be updated by arbitrary insertions or deletions of edges/vertices. Our goal is to efficiently compute structural clustering results under three conditions: 1) for any clustering parameters ϵ and μ provided on the fly, 2) for arbitrary graph update patterns, and 3) for all typical similarity measurements. To achieve this, we propose an algorithm named VD-STAR that is much simpler yet more efficient than state of the art. With a theoretical guarantee on clustering result's quality, VD-STAR can produce clustering results with up to 99.9% accuracy. Moreover, VD-STAR is easy to implement as it just needs to maintain s..